/**
 * 双向链表
 **/

export  class LinkList<T> {

    private _head: LinkListNode<T>;
    private _size: number = 0;

    public constructor() {
    }

    get First(): LinkListNode<T> {
        return this._head;
    }

    get Last(): LinkListNode<T> {
        return this._head != null ? this._head.prev : null;
    }

    AddAfter(node: LinkListNode<T>, value: T): LinkListNode<T> {
        this.ValidateNode(node);
        let newnode: LinkListNode<T> = new LinkListNode<T>(node.list, value);
        this.InsertNodeBefore(node.next, newnode);
        return newnode;
    }

    AddAfter2(node: LinkListNode<T>, newNode: LinkListNode<T>): void {
        this.ValidateNode(node);
        this.ValidateNewNode(newNode);
        this.InsertNodeBefore(node.next, newNode);
    }

    AddBefore(node: LinkListNode<T>, value: T): LinkListNode<T> {
        this.ValidateNode(node);
        let newNode: LinkListNode<T> = new LinkListNode<T>(node.list, value);
        this.InsertNodeBefore(node, newNode);
        if (node == this._head)
            this._head = newNode;
        return newNode;
    }

    AddBefore2(node: LinkListNode<T>, newNode: LinkListNode<T>): void {
        this.ValidateNode(node);
        this.ValidateNewNode(newNode);
        this.InsertNodeBefore(node, newNode);
        newNode.list = this;
        if (node != this._head)
            return;
        this._head = newNode;
    }

    AddFirst(value: T): LinkListNode<T> {
        let newNode: LinkListNode<T> = new LinkListNode<T>(this, value);
        if (this._head == null) {
            this.InsertNodeToEmptyList(newNode);
        } else {
            this.InsertNodeBefore(this._head, newNode);
            this._head = newNode;
        }
        return newNode;
    }

    AddFirst2(node: LinkListNode<T>): void {
        this.ValidateNewNode(node);
        if (this._head == null) {
            this.InsertNodeToEmptyList(node);
        } else {
            this.InsertNodeBefore(this._head, node);
            this._head = node;
        }
        node.list = this;
    }

    AddLast(value: T): LinkListNode<T> {
        let newNode: LinkListNode<T> = new LinkListNode<T>(this, value);
        if (this._head == null)
            this.InsertNodeToEmptyList(newNode);
        else
            this.InsertNodeBefore(this._head, newNode);
        return newNode;
    }

    AddLast2(node: LinkListNode<T>): void {
        this.ValidateNewNode(node);
        if (this._head == null)
            this.InsertNodeToEmptyList(node);
        else
            this.InsertNodeBefore(this._head, node);
        node.list = this;
    }

    Contains(value: T): boolean {
        return this.Find(value) != null;
    }

    CopyTo(array: T[], index: number): void {
        if (array == null)
            throw new Error('array is null')
        if (index < 0 || index > array.length)
            throw new Error('index is outside');
        if (array.length - index < this.Size())
            throw new Error("Arg_InsufficientSpace");
        let linkedListNode: LinkListNode<T> = this._head;
        if (linkedListNode == null)
            return;
        do {
            array[index++] = linkedListNode.item;
            linkedListNode = linkedListNode.next;
        }
        while (linkedListNode != this._head);
    }


    FindLast(value: T): LinkListNode<T> {
        if (this._head == null)
            return null;
        let prev: LinkListNode<T> = this._head.prev;
        let linkedListNode: LinkListNode<T> = prev;
        if (linkedListNode != null) {
            if (value != null) {
                while (linkedListNode.item !== value) {
                    linkedListNode = linkedListNode.prev;
                    if (linkedListNode == prev)
                        return null;
                }
                return linkedListNode;
            }
            while (linkedListNode.item !== null) {
                linkedListNode = linkedListNode.prev;
                if (linkedListNode == prev)
                    return null;
            }
            return linkedListNode;
        }
        return null;
    }


    Clear() {
        let linkedListNode1 = this._head;
        while (linkedListNode1 != null) {
            let linkedListNode2 = linkedListNode1;
            linkedListNode1 = linkedListNode1.Next;
            linkedListNode2.Invalidate();
        }
        this._head = null;
        this._size = 0;
    }


    Empty(): boolean {
        return this._size === 0;
    }

    ForEach(func:(value:T)=>boolean):T{
        let linklistNode = this._head;
        if (linklistNode != null) {
            while (linklistNode.item != null) {
                linklistNode = linklistNode.next;
                 if(func(linklistNode.item)){
                     return linklistNode.item;
                 }
                if (linklistNode == this._head){
                    break;
                }
            }
        }
    }


    Find(element: T): LinkListNode<T> {
        let linklistNode = this._head;
        if (linklistNode != null) {
            if (element != null) {
                while (linklistNode.item === element) {
                    linklistNode = linklistNode.next;
                    if (linklistNode == this._head)
                        return null;
                }
                return linklistNode;
            }
            while (linklistNode.item != null) {
                linklistNode = linklistNode.next;
                if (linklistNode == this._head)
                    return null;
            }
            return linklistNode;
        }
        return null;
    }

    Remove(element: T): boolean {
        let node = this.Find(element);
        if (node == null) {
            return false;
        }
        this.RemoveNode(node);
        return true;
    }

    Remove2(node: LinkListNode<T>): void {
        //this.ValidateNode(node);
        this.RemoveNode(node);
    }

    RemoveFirst(): void {
        if (this._head == null)
            throw new Error("LinkedListEmpty");
        this.RemoveNode(this._head);
    }

    RemoveLast(): void {
        if (this._head == null)
            throw new Error("LinkedListEmpty");
        this.RemoveNode(this._head.prev);
    }

    Size(): number {
        return this._size;
    }

    /**
     * 插入一个新节点
     * @param node
     * @constructor
     */
    private InsertNodeToEmptyList(node: LinkListNode<T>) {
        node.next = node;
        node.prev = node;
        this._head = node;
        ++this._size;
    }

    private ValidateNode(node: LinkListNode<T>): void {
        if (node == null) {
            throw new Error('node is null');
        }
        if (node.list === this) {
            throw new Error("same list");
        }
    }

    private ValidateNewNode(node: LinkListNode<T>): void {
        if (node == null) {
            throw new Error('node is null');
        }
        // if (node.list == null) {
        //     throw new Error(" list is null");
        // }
    }

    private InsertNodeBefore(node: LinkListNode<T>, newnode: LinkListNode<T>) {
        newnode.next = node;
        newnode.prev = node.prev;
        node.prev.next = newnode;
        node.prev = newnode;
        ++this._size;
    }

    private RemoveNode(newnode: LinkListNode<T>): void {
        if (newnode.next == newnode) {
            this._head = null;
        } else {
            this._head.prev.next = newnode.next;
            this._head.next.prev = newnode.prev;
            if (this._head == newnode) {
                this._head = newnode.next;
            }
        }
        --this._size;
    }


}

export default class LinkListNode<T> {
    get List(): LinkList<T> {
        return this.list;
    }

    get Previous(): LinkListNode<T> {
        return this.prev != null && this != this.list.First ? this.prev : null;
    }


    get Next(): LinkListNode<T> {
        return this.next != null && this.next != this.list.First ? this.next : null;
    }

    get Value(): T {
        return this.item;
    }

    set Value(value: T) {
        this.item = value;
    }

    item: T;
    next: LinkListNode<T>;
    prev: LinkListNode<T>;
    list: LinkList<T>;

    constructor(list: LinkList<T>, value: T) {
        this.item = value;
        this.list = list;
    }



    Invalidate() {
        this.next = null;
        this.prev = null;
        this.list = null;
    }
}





